Codificarea unui arbore (Timisoara - pregatire, ian.1996)

 Un arbore binar complet poate fi reprezentat prin codificarea drumurilor de
la radacina la fiecare frunza utilizand cifrele binare 0 si 1 astfel: pentru
fiecare nod, muchiei catre fiul stang i se asociaza valoarea 0, iar muchiei
catre fiul drept valoarea 1.
De exemplu:
 pentru arborele

               A
            /    \
          B        C
        /   \    /   \
       D     E  F     G
            / \
           H   I

 drumurile de la radacina la fiecare frunza se codifica astfel:
   ABD:   00
   ABEH:  010
   ABEI:  011
   ACF:   10
   ACG:   11
 Arborele de mai sus poate fi reprezentat prin secventa de codificari
(00,010,011,10,11) sau prin numarul binar 000100111011 obtinut prin cocatena-
rea codificarilor.
 Se considera m cifre 0 si n cifre 1 (m,n<=50); sa se determine daca acestea
pot forma un numar binar care sa reprezinte un arbore binar complet si, in
caz afirmativ sa se reprezinte grafic arborele; in caz contrar sa se afiseze
un mesaj.
 Fisierul de intrare ziua6_2.inp poate contine mai multe seturi de date pe
linii consecutive, fiecare set de date continand numerele m si n de cifre 0
respectiv 1.
 In fisierul ziua6_2.out iesirile corespunzatoare seturilor de date de intrare
trebuiesc delimitate de cate un rand liber. Pentru un set de date de intrare,
fisierul de iesire trebuie sa contina un mesaj daca problema nu are solutie,
iar in caz contrar pe o linie numarul binar obtinut din cele m+n cifre, care
reprezinta un arbore binar complet si apoi reprezentarea grafica a 
acestuia, in mod caracter (coduri 32-127).

Exemplu. Pentru setul de date de intrare:
6 6
iesirea este:
000100111011
               A
            /    \
          B        C
        /   \    /   \
       D     E  F     G
            / \
           H   I
-------------------------------------------------------------
Rezolvare (Mihai Stroe):

  Se foloseste metoda backtracking.
  Se incearca la fiecare pas obtinerea unui arbore binar complet
  prin transformarea unui drum catre o frunza in doua drumuri,catre
  fiul stang si fiul drept al unui nod aflat in pozitia fostei frunze.
  Daca s-au folosit toate cifrele,s-a ajuns la solutie.

  Exemplu:
    0,10,11 ->00,01,10,11 sau 0,100,101,11 sau 0,10,110,111

  Nu am realizat decat afisarea in prima forma.

}


var f,fo:text;
    s:string;
    i,j,k,l,m,n,kk:byte;
    st,top:array[1..100]of byte;
    siruri:array[1..100]of string;
    b:boolean;
    frunze:array[1..50,1..50]of
           record
             m,n,lung:byte;
             info:array[1..6]of byte;
           end;

procedure recurs(m,n,k:byte);
var i,j:byte;
begin
  if n+m=0 then begin kk:=k-1;b:=true;exit;end;
  if b=true then exit;
  for i:=1 to top[k-1]do
      if (frunze[k-1,i].m<m)and(frunze[k-1,i].n<n)then
         begin
           if b=true then exit;
           for j:=1 to i-1 do frunze[k,j]:=frunze[k-1,j];
           for j:=i+1 to top[k-1]do frunze[k,j-1]:=frunze[k-1,j];
           top[k]:=top[k-1]+1;
           frunze[k,top[k]-1]:=frunze[k-1,i];
           frunze[k,top[k]]:=frunze[k-1,i];
           inc(frunze[k,top[k]].n);
           inc(frunze[k,top[k]].lung);
           frunze[k,top[k]].info[frunze[k,top[k]].lung]:=1;
           inc(frunze[k,top[k]-1].m);
           inc(frunze[k,top[k]-1].lung);
           frunze[k,top[k]-1].info[frunze[k,top[k]-1].lung]:=0;
           recurs(m-frunze[k-1,i].m-1,n-frunze[k-1,i].n-1,k+1);
         end;
end;


procedure solve;
begin
  b:=false;
  fillchar(frunze,sizeof(frunze),0);
  if (n=0)or(m=0) then begin writeln(fo,'Problema nu are solutie ');writeln(fo);exit;end;
  k:=2;dec(m);dec(n);
  frunze[1,1].m:=1;
  frunze[1,1].n:=0;
  frunze[1,1].lung:=1;
  frunze[1,2].info[1]:=1;
  frunze[1,2].m:=0;
  frunze[1,2].n:=1;
  frunze[1,2].lung:=1;
  top[1]:=2;
  recurs(m,n,2);
  if not b then begin writeln(fo,'Problema nu are solutie ');writeln(fo);end
     else
       begin
         k:=kk;
         for i:=1 to top[k]do
             begin
               siruri[i]:='';
               for j:=1 to frunze[k,i].lung do
                   if frunze[k,i].info[j]=1 then siruri[i]:=siruri[i]+'1'
                                            else siruri[i]:=siruri[i]+'0';
             end;
               for i:=2 to top[k] do
                   for j:=1 to i-1 do
                       if siruri[i]<siruri[j] then
                          begin
                            s:=siruri[i];
                            siruri[i]:=siruri[j];
                            siruri[j]:=s;
                          end;
               write(fo,siruri[1],' ');
               for i:=2 to top[k] do
                   begin
                     write(fo,siruri[i],' ');
                     siruri[1]:=siruri[1]+siruri[i];
                   end;
               writeln(fo);
               writeln(fo,siruri[1]);
               writeln(fo);
       end;
end;

procedure readdata;
begin
  write('Introduceti numele fisierului de intrare ');
  readln(s);
  assign(f,s);
  reset(f);
  while not eof(f)do
        begin
          readln(f,m,n);
          solve;
        end;
  close(f);
end;

begin
  assign(fo,'ziua6_2.out');
  rewrite(fo);
  readdata;
  close(fo);
end.
